<!--
 * @Author: your name
 * @Date: 2021-12-01 14:59:33
 * @LastEditTime: 2021-12-07 15:50:07
 * @LastEditors: Please set LastEditors
 * @Description: 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 * @FilePath: \front-end-algorithm\算法\二叉树基础数据.html
-->
<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>二叉树-基础数据构造</title>
</head>

<body>

    <p>基本二叉排序树的特点：</p>
    <ul>
        <li>有序的树。</li>
        <li>若左子树不为空，则左子树的所有节点均小于它的根节点的值。</li>
        <li>若它的右子树不为空，则右子树的所有节点均大于它的根节点。</li>
        <li>左右子树也分别为二叉排序树。</li>
    </ul>
    <script>
        //二叉树的基础数据结构
        class Node {
            constructor(data, leftTree, rightTree) {
                this.data = data;
                this.leftTree = leftTree;
                this.rightTree = rightTree;
                this.count = 1;
            }
        }

        class BaseTree {
            constructor() {
                this.root = null;
            }

            //删除一个节点
            _removeNode(node, data) {
                if (node == null) {
                    return null;
                }
                if (data == node.data) {
                    //叶子节点
                    if (node.leftTree == null && node.rightTree == null) {
                        return null;
                    }

                    //没有右节点的节点
                    if (node.rightTree == null) {
                        return node.leftTree;
                    }

                    //有两个节点的节点
                    /**
                     * 做法：找到待删除节点的右子树上的最小值创建一个临时节点
                     * 将临时节点上的值复制到待删除节点，然后再删除临时节点
                     * 
                     * **/
                    //寻找右边子树的最小值

                    let tempNode = this.getMinNode(node.rightTree);
                    node.data = tempNode.data;
                    node.rightTree = this._removeNode(node.rightTree, tempNode.data);

                    return node;
                } else if (data < node.data) {
                    node.leftTree = this._removeNode(node.leftTree, data);
                    return node;
                } else {
                    node.rightTree = this._removeNode(node.rightTree, data);
                    return node;
                }
            }
            //删除指定节点
            remove(data) {
                this.root = this._removeNode(this.root, data)
            }
            //向二叉树插入节点
            insert(data) {
                //
                let newNode = new Node(data, null, null);

                if (this.root == null) {
                    this.root = newNode;

                } else {
                    let currentNode = this.root;
                    let parentNode = null;
                    while (true) {
                        parentNode = currentNode;
                        if (newNode.data < currentNode.data) {
                            currentNode = currentNode.leftTree;
                            if (!currentNode) {
                                parentNode.leftTree = newNode;
                                break;
                            }
                        } else if (newNode.data > currentNode.data) {
                            currentNode = currentNode.rightTree;
                            if (!currentNode) {
                                parentNode.rightTree = newNode;
                                break;
                            }
                        } else if (newNode.data == currentNode.data) {

                            // 如果给定的数据再次出现，就更新计数值
                            currentNode.count++;
                            break;
                        }
                    }
                }
            }
            //寻找给定数据节点
            find(data) {
                let currentNode = this.root;
                while (currentNode) {
                    if (currentNode.data == data) {
                        return currentNode
                    } else if (currentNode.data = data) {
                        currentNode = currentNode.leftTree;
                    } else if (currentNode.data < data) {
                        currentNode = currentNode.rightTree;
                    }
                }
                return null;
            }
            //获得最小值节点
            getMinNode(node = this.root) {

                let currentNode = node;
                while (currentNode.leftTree) {
                    currentNode = currentNode.leftTree;
                }

                return currentNode;
            }
            //获取最大值节点
            getMaxNode(node = this.root) {
                let currentNode = node;
                while (currentNode.rightTree) {
                    currentNode = currentNode.rightTree;
                }

                return currentNode;
            }
        }
        //二叉树---测试
        let myTree = new BaseTree();
        myTree.insert(20);
        myTree.insert(13);
        myTree.insert(7);
        myTree.insert(9);
        myTree.insert(15);
        myTree.insert(14);
        myTree.insert(42);
        myTree.insert(22);
        myTree.insert(21);
        myTree.insert(24);
        myTree.insert(57);

        console.log('输出二叉树：', myTree);
       /*  console.log(myTree.getMinNode());
          console.log(myTree.getMaxNode());
          myTree.remove(57);
          myTree.remove(42);
          console.log(myTree.getMaxNode());
          console.log(myTree); 
          
          from:https://zhuanlan.zhihu.com/p/109979290
          */

    </script>
</body>

</html>